#ifndef POLYLINE_SIMPLIFICATION_H_
#define POLYLINE_SIMPLIFICATION_H_

double pow_2(double x) 
{
   return x * x;
}

struct Point 
{
   double x, y;
   Point() {};
   Point(double x_, double y_): x(x_), y(y_) {};
};

std :: istream& operator>>(std::istream& in, Point& a)
{
   in >> a.x >> a.y;
   return in;
}

double distance_2(Point& a, Point& b) 
{
   return pow_2(a.x - b.x) + pow_2(a.y - b.y);
}

struct Segment 
{
   Point a, b;
   Segment(Point a_, Point b_): a(a_), b(b_) {};
   double length_2() 
   {	
      return pow_2(b.y - a.y) + pow_2(a.x - b.x);
   }
};

double dist_2(Point& p, Segment& s) 
{
   double d_2 = pow_2(p.x * (s.b.y - s.a.y) + p.y * (s.a.x - s.b.x) + s.b.x * s.a.y - s.a.x * s.b.y) / s.length_2();

   double min_2 = distance_2(p, s.b);
   double max_2 = distance_2(p, s.a);
     
   if (max_2 < min_2)
      std::swap(min_2, max_2);

   return max_2 - d_2 > s.length_2() ? min_2 : d_2;
}

int simplification(Point * point_list, bool* res, double eps, int left, int right) 
{    
   Segment s = Segment(point_list[left], point_list[right]);
   double d_max = 0;
   int mid = 0;
   for (int i = left + 1; i < right; i++) 
   {
      double d = dist_2(point_list[i], s);
      if ((d_max < d) && (d > eps)) 
      {
         d_max = d;
         mid = i;
      }
   }
   if (d_max != 0) 
   {
      res[mid] = true;
      size_t size = 1;
      size += simplification(point_list, res, eps, left, mid);
      size += simplification(point_list, res, eps, mid, right);
      return size;
   } 
   else 
      return 0;

}

int DP(Point * point_list, bool* res, int n, double eps) 
{
   res[n - 1] = true;
   res[0] = true;
   for (size_t i = 1; i < n - 1; ++i)
      res[i] = false;
   return simplification(point_list, res, eps, 0, n - 1) + 2;
}

#endif